#include <stdio.h>
//图的应用之最小生成树之普里姆算法
#define MAXSIZE 100
#define MAX 0x7fffffff  //int类型最大值
typedef char ElemType;
//图的声明
typedef struct 
{
    ElemType vertex[MAXSIZE];
    int edge[MAXSIZE][MAXSIZE];
    int vertex_num;
    int edge_num;
}mat_graph;
//图的创建
void creatgraph(mat_graph *g)
{
    g->vertex_num=9;
    g->edge_num=15;
    g->vertex[0]='A';
    g->vertex[1]='B';
    g->vertex[2]='C';
    g->vertex[3]='D';
    g->vertex[4]='E';
    g->vertex[5]='F';
    g->vertex[6]='G';
    g->vertex[7]='H';
    g->vertex[8]='I';
    int i,j;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<g->vertex_num;j++)
        {
            if(i==j)
            {
                g->edge[i][j]=0;
            }
            else
            {
                g->edge[i][j]=MAX;
            }
        }
    }
    //A-B A-F
    g->edge[0][1]=10;
    g->edge[0][5]=11;
    //B-C B-G B-I
    g->edge[1][2]=18;
    g->edge[1][6]=16;
    g->edge[1][8]=12;
    //C-D C-I
    g->edge[2][3]=22;
    g->edge[2][8]=8;
    //D-E D-G D-H D-I
    g->edge[3][4]=20;
    g->edge[3][6]=24;
    g->edge[3][7]=16;
    g->edge[3][8]=21;
    //E-F E-H
    g->edge[4][5]=26;
    g->edge[4][7]=7;
    //F-G
    g->edge[5][6]=17;
    //G-H
    g->edge[6][7]=19;
    for(i=0;i<g->vertex_num;i++)
    {
        for(j=0;j<i;j++)
        {
            g->edge[i][j]=g->edge[j][i];
        }
    }
}
//用普里姆算法生成最小生成树
void prim(mat_graph *g)
{
    int weight[MAXSIZE]={0};  //候选边的权值，vex_index数组的值和下标两个顶点相连的边的权值放在weight数组同一下标的元素中（一一对应）
    int vex_index[MAXSIZE]={0};  //值代表一个顶点，下标代表一个顶点，代表两个顶点相连了
    int i,j; //用来循环，i表示行数，j表示weight数组每个元素
    int min; //存放最小权值
    int k; //用来存放最小权值的下标,当发现weight数组权值最小且不为0时，去遍历以对应下标为行数的边数组
    for(i=0;i<g->vertex_num;i++)
    {
        weight[i]=g->edge[0][i];  //把A传过去，在A的基础上比较改动
    }
    for(i=1;i<g->vertex_num;i++)  //i=1是因为除去A自己那一行，因为上面已传过去了，要把剩下的每一行都跟weight作比较
    {
        min=MAX;//存放最小权值
        k=0; //因为每一次都要去找新的最小权值和坐标，所以要让他们重新初始化
        //找到每一次新的最小权值及坐标
        for(j=0;j<g->vertex_num;j++)
        {
            if(weight[j]!=0&&weight[j]<min)
            {
                min=weight[j];
                k=j; //1 //5 //8 //2 //6 //7 //4 //3
            }
        }
        printf("(%c %c)",g->vertex[vex_index[k]],g->vertex[k]); //AB AF BI IC BG GH HE HD
        weight[k]=0;  //证明这条线已经连完了，不能作为后面的待选路径
        //找新连接结点的待选路径
        for(j=0;j<g->vertex_num;j++)
        {
            if(weight[j]!=0&&g->edge[k][j]<weight[j])  //把每一行都跟weight作比较，在过程中就巧妙避开环的形成
            {
                weight[j]=g->edge[k][j];
                vex_index[j]=k;
            }
        }
    }
}
int main()
{
    mat_graph g;
    creatgraph(&g);
    prim(&g);
    return 0;
}
//输出：(A B)(A F)(B I)(I C)(B G)(G H)(H E)(H D)